package leetcode.editor.cn.q1_300.q150;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author qidi
 * @date 2022-02-25 11:01:05
 */
class Q0187_RepeatedDnaSequences {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<String> findRepeatedDnaSequences(String s) {
            int n = s.length();
            if (n < 10) return new ArrayList<>();

            Set<String> ans = new HashSet<>();
            Set<String> set = new HashSet<>();
            for (int i = 10; i <= n; i++) {
                String sub = s.substring(i - 10, i);
                if (set.contains(sub)) {
                    ans.add(sub);
                }
                set.add(sub);
            }

            return new ArrayList<>(ans);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0187_RepeatedDnaSequences().new Solution();
        System.out.println(solution.findRepeatedDnaSequences("AAAAAAAAAAA"));
        System.out.println(solution.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"));
        System.out.println(solution.findRepeatedDnaSequences("AAAAAAAAAAAAA"));
    }
}